SCAN Disk Scheduling Algorithm

• As the name suggests, this algorithm scans all the cylinders of the disk back and forth.
• Head starts from one end of the disk and move towards the other end servicing all the requests in between.
• After reaching the other end, head reverses its direction and move towards the starting end servicing all the requests in between.
• The same process repeats.

Advantages

• It is simple, easy to understand and implement.
• It does not lead to starvation.
• It provides low variance in response time and waiting time.

Disadvantages

• It causes long waiting time for the cylinders just visited by the head.
• It causes the head to move till the end of the disk even if there are no requests to be serviced.

---

def scan(arr: list, start: int, RANGE: tuple, upDirection = True, log = False) -> int:
    if upDirection == True:
        rotations = RANGE[1] - start
        t = min(arr)
        rotations += (RANGE[1] - t)
        if log == True:
            print(f'({RANGE[1]} - {start}) + ({RANGE[1]} - {t}) = {rotations}')
        return rotations
    else:
        rotations = start - RANGE[0]
        t = max(arr)
        rotations += (t - RANGE[0])
        if log == True:
            print(f'({start} - {RANGE[0]}) + ({t} - {RANGE[0]}) = {rotations}')
        return rotations

C-SCAN Disk Scheduling Algorithm

• Circular-SCAN Algorithm is an improved version of the SCAN Algorithm.
• Head starts from one end of the disk and move towards the other end servicing all the requests in between.
• After reaching the other end, head reverses its direction.
• It then returns to the starting end without servicing any request in between.
• The same process repeats.

Advantages

• The waiting time for the cylinders just visited by the head is reduced as compared to the SCAN Algorithm.
• It provides uniform waiting time.
• It provides better response time.

Disadvantages

• It causes more seek movements as compared to SCAN Algorithm.
• It causes the head to move till the end of the disk even if there are no requests to be serviced.

---

def c_scan(arr: list, start: int, RANGE: tuple, upDirection = True, log = False) -> int:
    t1 = max(arr)
    t2 = min(arr)

    # edge conditions first
    if t1 < start:
        if upDirection:
            rotations = (start - RANGE[0]) + (t1 - RANGE[0])
            if log == True:
                print(f'({start} - {RANGE[0]}) + ({t1} - {RANGE[0]}) = {rotations}')
            return rotations
        
        else:
            rotations = start - RANGE[0]
            if log == True:
                print(f'{start} - {RANGE[0]} = {rotations}')
            return rotations
        
    if start < t2:
        if upDirection:
            rotations = RANGE[1] - start
            if log == True:
                print(f'{RANGE[1]} - {start} = {rotations}')
            return rotations
        
        else:
            rotations = (start - RANGE[0]) + (t1 - RANGE[0])
            if log == True:
                print(f'({start} - {RANGE[0]}) + ({t1} - {RANGE[0]}) = {rotations}')
            return rotations
    
    if upDirection == True:
        rotations = abs(RANGE[1] - start)
        firstMaxIndex = max([i for i in arr if i < start])
        rotations += ((RANGE[1] - RANGE[0]) + (firstMaxIndex - RANGE[0]))

        if log == True:
            print(f'({RANGE[1]} - {start}) + ({RANGE[1]} - {RANGE[0]}) + ({firstMaxIndex} - {RANGE[0]}) = {rotations}')
        return rotations
    else:
        rotations = abs(start - RANGE[0])
        lastMaxIndex = min([i for i in arr if i > start])
        rotations += ((RANGE[1] - RANGE[0]) + (RANGE[1] - lastMaxIndex))

        if log == True:
            print(f'({start} - {RANGE[0]}) + ({RANGE[1]} - {RANGE[0]}) + ({RANGE[1]} - {lastMaxIndex}) = {rotations}')
        return rotations

LOOK Disk Scheduling Algorithm

• LOOK Algorithm is an improved version of the SCAN Algorithm.
• Head starts from the first request at one end of the disk and moves towards the last request at the other end servicing all the requests in between.
• After reaching the last request at the other end, head reverses its direction.
• It then returns to the first request at the starting end servicing all the requests in between.
• The same process repeats.

NOTE

• The main difference between SCAN Algorithm and LOOK Algorithm is.
• SCAN Algorithm scans all the cylinders of the disk starting from one end to the other end even if there are no requests at the ends.
• LOOK Algorithm scans all the cylinders of the disk starting from the first request at one end to the last request at the other end.

Advantages

• It does not cause the head to move till the ends of the disk when there are no requests to be serviced.
• It provides better performance as compared to SCAN Algorithm.
• It does not lead to starvation.
• It provides low variance in response time and waiting time.

Disadvantages

• There is an overhead of finding the end requests.
• It causes long waiting time for the cylinders just visited by the head.

def look(arr: list, start: int, upDirection = True, log = False) -> int:
    t1 = max(arr)
    t2 = min(arr)

    # edge conditions first
    if t1 < start:
        rotations = start - t2
        if log == True:
            print(f'{start} - {t2} = {rotations}')
        return rotations
        
    if start < t2:
        rotations = t1 - start
        if log == True:
            print(f'{t1} - {start} = {rotations}')
        return rotations
    
    if upDirection == True:
        rotations = t1 - start
        rotations += (t1 - t2)
        if log == True:
            print(f'({t1} - {start}) + ({t1} - {t2}) = {rotations}')
        return rotations

    else:
        rotations = start - t2
        rotations += (t1 - t2)
        if log == True:
            print(f'({start} - {t2}) + ({t1} - {t2}) = {rotations}')
        return rotations

C-LOOK Disk Scheduling Algorithm

• Circular-LOOK Algorithm is an improved version of the LOOK Algorithm.
• Head starts from the first request at one end of the disk and moves towards the last request at the other end servicing all the requests in between.
• After reaching the last request at the other end, head reverses its direction.
• It then returns to the first request at the starting end without servicing any request in between.
• The same process repeats.

Advantages

• It does not causes the head to move till the ends of the disk when there are no requests to be serviced.
• It reduces the waiting time for the cylinders just visited by the head.
• It provides better performance as compared to LOOK Algorithm.
• It does not lead to starvation.
• It provides low variance in response time and waiting time.

Disadvantages

• There is an overhead of finding the end requests.

def c_look(arr: list, start: int, upDirection = True, log = False) -> int:
    t1 = max(arr)
    t2 = min(arr)

    # edge conditions first
    if t1 < start:
        if upDirection:
            rotations = (start - t2) + (t1 - t2)
            if log == True:
                print(f'({start} - {t2}) + ({t1} - {t2}) = {rotations}')
            return rotations
        
        else:
            rotations = start - t2
            if log == True:
                print(f'{start} - {t2} = {rotations}')
            return rotations
        
    if start < t2:
        if upDirection:
            rotations = t1 - start
            if log == True:
                print(f'{t1} - {start} = {rotations}')
            return rotations
        
        else:
            rotations = (start - t2) + (t1 - t2)
            if log == True:
                print(f'({start} - {t2}) + ({t1} - {t2}) = {rotations}')
            return rotations
    
    if upDirection == True:
        rotations = abs(t1 - start)
        firstMaxIndex = max([i for i in arr if i < start])
        rotations += ((t1 - t2) + (firstMaxIndex - t2))

        if log == True:
            print(f'({t1} - {start}) + ({t1} - {t2}) + ({firstMaxIndex} - {t2}) = {rotations}')
        return rotations
    else:
        rotations = abs(start - t2)
        lastMaxIndex = min([i for i in arr if i > start])
        rotations += ((t1 - t2) + (t1 - lastMaxIndex))

        if log == True:
            print(f'({start} - {t2}) + ({t1} - {t2}) + ({t1} - {lastMaxIndex}) = {rotations}')
        return rotations

currentHead = 53
trackRange = (0, 199)
requestArray = [98, 183, 41, 122, 14, 124, 65, 67]

Questions

Q1. Consider a disk queue with requests for I/O to blocks on cylinders $\ 98, 183, 41, 122, 14, 124, 65, 67\ $. The SCAN scheduling algorithm is used. The head is initially at cylinder number $53$ moving towards larger cylinder numbers on its servicing pass. The cylinders are numbered from $0$ to $199$. The total head movement (in number of cylinders) incurred while servicing these requests is _______

print(f'Total number of head movements = {scan(requestArray, currentHead, trackRange, upDirection = True, log = True)}')

(199 - 53) + (199 - 14) = 331
Total number of head movements = 331

---

Q2. Consider a disk queue with requests for I/O to blocks on cylinders $\ 98, 183, 41, 122, 14, 124, 65, 67\ $. The C-SCAN scheduling algorithm is used. The head is initially at cylinder number $53$ moving towards larger cylinder numbers on its servicing pass. The cylinders are numbered from $0$ to $199$. The total head movement (in number of cylinders) incurred while servicing these requests is _______

print(f'Total number of head movements = {c_scan(requestArray, currentHead, trackRange, upDirection = True, log = True)}')

(199 - 53) + (199 - 0) + (41 - 0) = 386
Total number of head movements = 386

---

Q3. Consider a disk queue with requests for I/O to blocks on cylinders $\ 98, 183, 41, 122, 14, 124, 65, 67\ $. The LOOK scheduling algorithm is used. The head is initially at cylinder number $53$ moving towards larger cylinder numbers on its servicing pass. The cylinders are numbered from $0$ to $199$. The total head movement (in number of cylinders) incurred while servicing these requests is _______

print(f'Total number of head movements = {look(requestArray, currentHead, upDirection = True, log = True)}')

(183 - 53) + (183 - 14) = 299
Total number of head movements = 299

---

Q4. Consider a disk queue with requests for I/O to blocks on cylinders $\ 98, 183, 41, 122, 14, 124, 65, 67\ $. The C-LOOK scheduling algorithm is used. The head is initially at cylinder number $53$ moving towards larger cylinder numbers on its servicing pass. The cylinders are numbered from $0$ to $199$. The total head movement (in number of cylinders) incurred while servicing these requests is _______

print(f'Total number of head movements = {c_look(requestArray, currentHead, upDirection = True, log = True)}')

(183 - 53) + (183 - 14) + (41 - 14) = 326
Total number of head movements = 326

---

Q5. Consider a disk queue with requests for I/O to blocks on cylinders $\ 47, 38, 121, 191, 87, 11, 92, 10\ $. The C-LOOK scheduling algorithm is used. The head is initially at cylinder number $63$ moving towards larger cylinder numbers on its servicing pass. The cylinders are numbered from $0$ to $199$. The total head movement (in number of cylinders) incurred while servicing these requests is _______

currentTrack = 63
requestArray = [47, 38, 121, 191, 87, 11, 92, 10]

print(f'Total number of head movements = {c_look(requestArray, currentTrack, upDirection = True, log = True)}')

(191 - 63) + (191 - 10) + (47 - 10) = 346
Total number of head movements = 346

---